A novel approach to estimating the detailed shape of arbitrary extended objects jointly with their kinematics in the absence of a priori information is presented. The proposed shape model represents the tightest enclosing bound of the object projected into the ego motion plane as a polygon with an unknown number of vertices. Probabilistic inference techniques are employed to overcome various sources of uncertainty by rigorously estimating the joint distribution over the object shape and kinematic states, rather than estimating these variables directly. Simulation and experimental results are presented for objects with complex shapes tracked from an autonomous vehicle research platform. In addition to providing a richer set of information for higher level reasoning about extended objects (e.g. about object type, or occupied space), the results demonstrate that detailed shape estimates enable efficient use of sensor information by way of explicit surface-based sensor models; this efficient use of sensor information improves observability of latent object states, thereby improving tracking precision.