The aim of this research is to conduct an analysis of the influence of relationship marketing and perceived quality on increasing consumer loyalty at one of the frozen shrimp processing companies located in East Java. Based on the results of data analysis that has been carried out on the first hypothesis (H1) which states that relationship marketing has a positive and significant effect on increasing consumer loyalty, the calculated t value is 17,163, which is greater than the t table value, which is 1,661, the results of the calculation analysis of the second hypothesis (H2) which states that perceived quality has a positive and significant effect on increasing customer loyalty, obtained a calculated t value of 6,597 which is greater than the t table value of 1,661, which means that relationship marketing and perceived quality have a positive and significant effect on increasing customer loyalty, while the R-square value obtained was 0.809, which stated that the relationship marketing and perceived quality variables had an effect on increasing customer loyalty by 80.90% and the remaining 19.10% was influenced by other variables.