Recently proposed full-diversity space-time-frequency block codes (STFBCs) generally suffer from very high computational complexity at the receiver side. In this paper, we introduce a new class of full-diversity STFBCs for quasi-static (QS) channels which features a comparatively low complexity at the receiver. We also demonstrate that our proposed algorithms could offer maximum coding advantage if the transmitter knows partial channel side information. Simulation results also verify that our coding schemes outperform other recently published STFBCs that were considered.