Antimony (Sb) nanoparticles dispersed in a hybrid matrix consisting of aluminum (Al) and carbon, AlC0.75-C were synthesized via one-step high-energy mechanical milling (HEMM) process and assessed as potential anode materials for use in sodium-ion batteries. The introduction of carbon during HEMM led to the formation of individual Sb nanoparticles dispersed in the AlC0.75-C matrix; in the absence of carbon during HEMM, an AlSb alloy was formed. The Sb-AlC0.75-C composite anodes demonstrated better cycling performance as well as higher rate capability compared to an AlSb anode; these improved properties could be due to the well-developed Sb phase, which acts as an electrochemically active nanocrystalline material in the AlC0.75/carbon conductive matrix. Furthermore, when fluoroethylene carbonate (FEC) was added to the electrolyte, the sodium-ion cells exhibited the best electrochemical performances, corresponding to a capacity retention of 83% at 100 cycles at 100 mA g−1 and a high rate capacity retention of 58% at 5000 mA g−1. In addition, the as-prepared Sb-AlC0.75-C composite has a high tap density; thus, its volumetric capacity was approximately three times that of carbon.