We report the discovery of 39 faint high-latitude carbon stars (FHLCs) from Sloan Digital Sky Survey (SDSS) commissioning data. The objects, each selected photometrically and verified spectroscopically, range over 16.6<r*<20.0 and show a diversity of temperatures as judged by both colors and NaD line strengths. Although a handful of these stars were previously known, these objects are, in general, too faint and too warm to be effectively identified in other modern surveys such as the Two Micron All Sky Survey, nor are their red/near-IR colors particularly distinctive. We present proper-motion measures for each object, indicating that the sample is a mixture of extremely distant (greater than 100kpc) halo giant stars, useful for constraining halo dynamics, and members of the recently recognized exotic class of very nearby dwarf carbon (dC) stars.