We study the velocity and shape of air bubbles rising through a transparent yield-stress fluid. The bubbles are small enough compared to the experimental vessel that effects of walls are weak. We find that the terminal rise velocity of the bubbles increases approximately linearly with bubble radius over the range of volumes accessible in our experiments. We observe bubble motion only when the bubbles are larger than a certain critical radius. In terms of a dimensionless yield parameter Y, the ratio between the force due to the yield stress and the buoyant force, we observe bubble motion only for Y less than or similar to 0.50 +/- 0.04. The bubbles are non-spherical, having the shape of an inverted teardrop with a rounded head and a cusp-like tail. The cusps may be an indication that elasticity plays a significant role in this system. By fitting the cross-sectional radius of the bubble as a function of the axial coordinate to an empirical function, we study the dependence of the bubble shape on volume and the yield stress of the material. (C) 2008 Elsevier B.V. All rights reserved.