한국전쟁으로 부산이 대한민국 임시 수도가 되고, 1951년 1 · 4후퇴를 거치면서 많은 실향민들이 부산에 정착하게 되었다. 기존에 한국인이 먹던 냉면은 메밀이 주원료이지만, 한국전쟁 이후 메밀이 구하기 어려워지고, 미군들의 구호물자로 밀가루가 흔해지면서, 밀가루에 고구마 전분을 섞어 면을 뽑아 먹기 시작하게 된 것이 부산밀면의 시초라 할 수 있다. 처음에는 밀면을 밀냉면, 부산 냉면, 경상도 냉면이라고도 불렀는데 밀냉면을 줄인 밀면이라는 용어로 정착되었다.
보통 밀가루로 만든 면 요리는 뜨겁게 먹지만, 밀면은 찬 육수에 말아 먹는 음식이다. 일반적으로 밀가루만을 재료로 만든 국수의 성형 자체는 어렵지 않지만 녹말가루로 만든 것보다 쫄깃한 질감이 떨어진다. 이를 보완하기 위하여 압착식으로 면발을 뽑아 끓는 물에 삶아내고, 냉수에 여러 번 비벼 씻는 과정을 거친다. 이 과정에서 표면 전분을 제거하고 호화의 진행을 막아 국숫발이 쫄깃한 질감의 밀면으로 태어나게 된다. 쫄깃한 면발을 만들기 위해 밀가루 중력분에 전분을 첨가하여 반죽하기도 한다. 특히 부산밀면은 밀가루에 소금을 넣어 반죽하여 하루 동안 숙성한 생면을 이용한다.
부산밀면은 생면에 육수를 붓고 볶은 오이, 식초, 고운 고춧가루, 다진 마늘, 소금, 설탕 등으로 양념한 무채, 배, 삶은 달걀과 돼지고기를 고명으로 올린다. 이때 육수는 소나 돼지의 사골 뼈, 닭 뼈나 쇠고기 양지 및 사태 부위를 고아 사용한다. 업소에 따라서는 여러 종류의 한약재, 채소류 등을 넣고 고아 사용하기도 한다. 비빔밀면은 고춧가루에 마늘, 양파 등을 다져 넣은 양념으로 비벼서 먹는데 매콤하면서도 달콤한 풍미를 즐길 수 있는 음식이다. 부산밀면은 경상도 입맛에 맞추어 다진 양념이 많이 들어가, 맵고 짠 자극적인 맛이 특징이다.