Autosomal recessive hereditary spastic paraplegia (HSP) due to AP4M1 mutations is a very rare neurodevelopmental disorder reported for only a few patients. We investigated a Greek HSP family using whole exome sequencing (WES). A novel AP4M1A frameshift insertion, and a very rare missense variant were identified in all three affected siblings in the compound heterozygous state (p.V174fs and p.C319R); the unaffected parents were carriers of only one variant. Patients were affected with a combination of: (a) febrile seizures with onset in the first year of life (followed by epileptic non-febrile seizures); (b) distinctive facial appearance (e.g., coarse features, bulbous nose and hypomimia); (c) developmental delay and intellectual disability; (d) early-onset spastic weakness of the lower limbs; and (e) cerebellar hypoplasia/atrophy on brain MRI. We review genotype-phenotype correlations and discuss clinical overlaps between different AP4-related diseases. The AP4M1 belongs to a complex that mediates vesicle trafficking of glutamate receptors, being likely involved in brain development and neurotransmission.