Observations of the 1(01)-0(00) rotational transitions of A and E state acetaldehyde are reported. The transitions were detected, for the first time in interstellar space, in the cold dust clouds TMC-1 and L134N, and in Sgr B2. This is also the first time acetaldehyde has been found in a dust cloud and is the most complex oxygen-bearing molecule yet known in this environment. A column density of 6 x 10 to the 12th/sq cm in TMC-1, comparable to many other species detected there, and an approximately equal column density in L134N are formed. In the direction of Sgr B2, the CH3CHO profile appears to consist of broad emission features from the hot molecular cloud core, together with absorption features resulting from intervening colder material. The possible detection of HC9N toward IRC + 10 deg 216 through its J = 33-32 transition is also reported. Implications for cold dust cloud chemistry and excitation are discussed.