改编
原著作者白桦当时是昆明军区创作组组长，新中国第一部反映少数民族生活、爱情及军民联合剿匪的电影《山间铃响马帮来》的剧本就是出自他手。他通过自己在边疆的实地生活，细心观察边寨的生活习俗，又在第二年写出了反特小说《一个无铃的马帮》（亦作《无铃的马帮》）。[1][1]导演林农看完后非常喜欢，亲自将其改编成电影剧本。由于当时提倡节约，摄制组无法到云南边境实地取景，于是在中朝边境一个叫四道沟的地方找到了外景地。场景中的芭蕉树是美术师刘学尧做出来的。[2][2]影片最初定名为《两个巡逻兵》，拍摄完后送到电影局审查。蔡楚生同志认为片子的主题、故事、人物、音乐特别是插曲搞得很新颖。可是片名《两个巡逻兵》不好，“像个纪录片。好电影，更应该有个好片名，要吸引观众，吸引观众来看电影！”根据故事的展开和人物的关系，他建议改名叫《神秘的旅伴》。[3][3]
选角
1955年元旦，大雪纷飞，导演林农、朱文顺在总政话剧团偶遇20岁的王晓棠，她身着红衣在操场练功，灵动身姿与出众气质让导演惊艳，力排众议启用这位无影视经验的新人。初涉影坛，王晓棠又遇到难题。该片在长春电影制片厂拍摄，那里藏龙卧虎，很多经验丰富的演员选角都没被选上，反而让她这个没有出镜经历的“生坯子”担纲主演，大家不服气。导演林农又是演员出身，对表演要求极高。刚开拍时，老说她演得“假”。王晓棠知道自己的不足，却不气馁。认准一个字“学”，不管见到谁，都虚心请教：“我没演过电影，请你告诉我应该注意什么。”电影插曲是先录音，再配画面。王晓棠必须精确掌握曲子的哪段旋律是第几号镜头，这个镜头是几秒钟，还必须在这几秒钟里完成准确的无言表演而依次递进。为了掌握它，她反复琢磨，摸索着怎样精进演技，观察摄影、美工、剪辑等工种的门道，像海绵一样快速吸收各种知识，进步神速。拍到朱大哥去追坏人，小黎英醒后发现人不见了的情节时，王晓棠一遍通过。连含蓄的林农也点头称赞：“戏要是都这么演还差不多。”就这样，小黎英唱着《缅桂花开十里香》走进了大众的心里。[4][4]
表演
