A relay channel is one in which a Source and Destination use an intermediate Relay station in order to improve communication rates. We propose the study of relay channels with classical inputs and quantum outputs and prove that a "partial decode and forward" strategy is achievable. We divide the channel uses into many blocks and build codes in a randomized, block-Markov manner within each block. The Relay performs a standard Holevo-Schumacher-Westmoreland quantum measurement on each block in order to decode part of the Source's message and then forwards this partial message in the next block. The Destination performs a novel "sliding-window" quantum measurement on two adjacent blocks in order to decode the Source's message. This strategy achieves non-trivial rates for classical communication over a quantum relay channel.