Purpose: This study examines the effect of cross-border logistics on shipping company performance in East Africa, specifically investigating how customs clearance efficiency, transportation management systems (TMS) adoption, last-mile delivery optimization, and supply chain coordination influence operational, financial, and market performance of maritime logistics firms in Mombasa County, Kenya. Methodology: The research employed a descriptive survey design with stratified random sampling of 172 shipping companies operating in Mombasa County. Data were collected through structured questionnaires from 149 respondents (86.63% response rate), yielding cross-sectional observations of logistics practices and performance outcomes. Multiple linear regression analysis examined the joint effects of independent variables on performance, controlling for firm size, years of operation, service scope, and customer profile. Results: All four hypothesized relationships were confirmed statistically (p < 0.05). Supply chain coordination demonstrated the strongest effect on performance (β = 0.458, standardized β = 0.338), followed by transportation management systems (β = 0.412, standardized β = 0.234), last-mile delivery optimization (β = 0.289, standardized β = 0.241), and customs clearance efficiency (β = 0.186, standardized β = 0.182). The regression model explained 77.2% of performance variance (R² = 0.772, F = 52.34, p < 0.001), indicating that cross-border logistics dimensions are critical performance determinants. However, technology adoption barriers limit TMS implementation to 34.2% of firms, representing untapped performance improvement opportunity. Theoretical Contribution: The study contributes to the logistics and supply chain management literature by providing firm-level empirical evidence on determinants of cross-border logistics performance in Sub-Saharan Africa, where such research remains limited. The integrated examination of multiple logistics dimensions reveals performance interdependencies. The findings extend institutional theory, the resource-based view, transaction cost economics, and network theory by demonstrating their complementary explanatory power in the context of logistics in developing economies. The dominant effect of supply chain coordination supports network theory predictions while highlighting limitations of technology-centered approaches in resource-constrained environments. Practical Implications: For shipping company executives, the research provides evidence-based guidance for strategic logistics investments, emphasizing that supply chain coordination and relationship development can yield higher returns than technology adoption alone. For policymakers, the findings support prioritizing customs reform, technology infrastructure investment, and regional harmonization within the East African Community and the African Continental Free Trade Area. For industry associations, the research identifies skills gaps in logistics management requiring capacity-building initiatives and suggests that collaborative problem-solving forums addressing inter-organizational coordination challenges would benefit industry competitiveness.