Terasi is a traditional fermented shrimp paste used in Indonesian dish as condiments. Due to its affordability, the paste is widely consumed among the general population, and thus has a great impact in Indonesia. Currently, small-scale or home industry is common for terasi production, and natural fermentation process is the traditional method. Fermentation process is considered finish when desired aromatic odors are obtained. But this makes the fermentation process subjective, because the decision is solely dependent on the producer. Additionally, natural fermentation poses a higher risk for contamination of microbial pathogens. As a result, the food safety and food taste quality of the final product varies greatly from region to region. Therefore, it is necessary to improve the quality of terasi by means of controlled fermentation. Quality improvement can yield safer products, and can change the terasi production process from small-scale to large-scale. Hence, the objective of the research is to improve the quality of terasi by determining the most optimal fermentation starter culture. Optimal fermentation conditions were determined by analyzing the effect of the various starter inoculum on the inner microbial community, and results indicated that mixed culture of Staphylococcus saprophyticus, Bacillus subtilis, and Lactobacillus murinus with ratio of 2:1:2 was the most effective for suppressing the growth of unwanted microorganisms. The difference in the microbial composition also led to a different metabolite profile. Compared to naturally fermented terasi, terasi inoculated with the optimized ratio broke down polymers, such as protein, into its monomers during earlier stage of fermentation.