Cities have been increasingly involved in the development of food policies, becoming key points in achieving food security and fostering the transition to sustainable agri-food systems. The aim of this paper is to identify citizens’ profiles by performing segmentation and profiling according to their socio-economic variables and perception of key factors affecting food security. This is to define appropriate strategies to guide policy makers in a more effective creation of urban food policies. An online survey was filled out by citizens of the Metropolitan City of Bari from July to November 2022. Descriptive analysis, principal component analysis and K-means cluster analysis were applied to the collected data. Four clusters of citizens were obtained and labelled based on socio-economic characteristics and key factors affecting food security perception. Specifically, the “Law-confident” (45% of citizens) and “Hedonist” (36%) clusters revealed the greatest trust in “governance” and “quality certification” aspects. The “Capitalist” (15%) and “Conservatory” (4%) clusters were relatively small groups, characterized respectively by a positive perception of the standardization of food production and governance power, with a focus on strategies regarding food policy implementation, reduction of food loss and waste (FLW) and improvement of food quality certifications systems. The proposed approach and results may support EU policy makers in identifying key macro-areas and matters toward which to direct public funding in order to improve food security in urban areas, and to put in place actions enhancing citizens’ knowledge and awareness of key issues of food security.