We present a simultaneous localization and mapping (SLAM) algorithm that uses Bézier curves as static landmark primitives rather than sparse feature points. Our approach allows us to estimate the full 6-DOF pose of a robot while providing a structured map which can be used to assist a robot in motion planning and control. We demonstrate how to reconstruct the 3-D location of curve landmarks from a stereo pair without searching for point-based stereo correspondences and how to compare the 3-D shape of curve landmarks between chronologically sequential stereo frames to solve the data association problem. We present a method to combine curve landmarks for mapping purposes, resulting in a map with a continuous set of curves that contain fewer landmark states than conventional sparse point-based SLAM algorithms. Note, to combine curves, we assume the curved landmarks are fixed to a larger curved object naturally occurring in the scene. While our algorithm is less accurate than point-based SLAM algorithms, we are able to create maps with considerably less landmark states and our algorithm can operate in settings lacking texture.