Speech translation for low-resource languages is constrained by the scarcity of high-quality parallel speech data, which is particularly pronounced in African linguistic contexts. To address this, we introduce , a parallel speech translation dataset covering Igbo, Hausa, , and Nigerian Pidgin paired with English. The dataset contains more than 40 hours of speech per language and includes several speaker and accent variations to reflect realistic settings. Using NaijaS2ST, we benchmark cascaded, end-to-end (E2E), and AudioLLM-based approaches across bidirectional translation directions (XX↔English). Our results show that few-shot audio LLMs are more effective than cascaded and E2E methods finetuned for speech-to-text translation. For speech-to-speech translation, however, cascaded and audio LLM paradigms perform comparatively, highlighting the need for stronger task-specific models. offers a strong foundation towards advancing research on low-resource multilingual speech translation. We open source the dataset here: [NaijaS2ST Huggingface Dataset](https://huggingface.co/datasets/McGill-NLP/NaijaS2ST); and the code here: [NaijaS2ST Code](https://github.com/McGill-NLP/naijas2st).