爱华网1958年7月28日，铁路合作组织关于协商国际联运旅客列车时刻表会议在波兰华沙举行，会议商定北京-莫斯科间直通旅客列车自1959年夏季起经由蒙古国每周运行1往返。1959年4月8日，中苏蒙铁路代表会议在苏联伊尔库茨克举行，就北京-乌兰巴托-莫斯科国际旅客列车的开行签订议定书，自1959年6月1日起生效。
1959年6月4日，北京-乌兰巴托-莫斯科国际旅客列车正式开行，车次被确定为3/4次，由苏联铁路提供车辆并担任客运乘务，列车在集宁站更换转向架。1960年5月24日，由中国铁路提供车辆并担任客运乘务的北京-乌兰巴托-莫斯科国际旅客列车开行，苏联铁路担当的列车停开。同年5月31日，首趟由中方担任的国际 联运客车抵达莫斯科雅罗斯拉夫火车站月台，以交通部长马斯维切夫为首的苏联各界人士到车站迎接。开行之初，中方主要学习苏联的经验，照抄对方的作业程序、排班制度。早年乘坐这趟列车的大多是因公出差的政府官员、代表团，甚至是省部级以上的高级干部。车辆在库内检修时有公安人员把守。故而不少人把这趟车称作“神秘的东方列车”。
虽然1960年代至1980年代间中苏交恶，3/4次列车仍然没有停运，但之间曾发生多次冲突，例如苏联扣押列车上的中国驻苏联外交官。1963年9月7日，由北京铁路局担当乘务的3次列车在苏联纳乌什基站遭到苏联边防和海关人员的无理检查，并在8日驱逐全体中国列车乘务员和旅客。事发后中国铁道部3次致电苏联交通部，要求对方采取措施，保证不再发生类似事件。16日，中国国务院总理周恩来、外交部长陈毅在北京人民大会堂接见列车全体乘务员，谴责苏方的无理行为。1965年10月12日，集二铁路由轨距1524毫米的宽轨改为1435毫米的标准轨，列车换装及换轮由集宁站改在二连站进行。中苏交恶期间，列车乘务员被要求不得擅自与外国旅客聊天，列车抵达境外车站时，不允许旅客下车拍照留念。中方列车员也怕犯政治错误，不敢和旅客合影，出境时除了《人民日报》不能携带其他报纸杂志。
1990年代苏联解体后，随着中俄关系快速发展和边贸热的兴起，往返于两国做生意的人员逐渐成为这趟列车的主要乘客，尤其是90年代初，坐车的大多是倒卖国际商品的投机商人，客车变成了“货车”。1998年10月中国铁路实现第二次大面积提速，列车车次在中国境内因此变更为K3/4次快速列车。
2000年代后，K3/4次列车的旅客构成也发生了很大变化，现在从莫斯科到北京来的旅客主要是西方旅游者，为的是欣赏沿途的风光，旺季时常常爆满，一票难求。
| 开行 | 1959年6月4日（每周1班） |
|---|---|
| 承运国 | 中华人民共和国 |
| 承运商 | 北京铁路局 |
| 列车等级 | 快速列车 |
| 曾用车次 | 3/4次（中国），1/2次（蒙古国）， 7/8次（俄罗斯） |
| 目前车次 | K3/4次（中国）, 003/004次（蒙古国、俄罗斯） |
| 运行区间 | 中国北京 ↔俄罗斯莫斯科 |
| 途经线路 | 京包铁路、集二铁路、蒙古纵贯铁路、 西伯利亚铁路 |
| 主要站点 | 乌兰巴托站、伊尔库茨克站、 新西伯利亚站、叶卡捷琳堡站 |
| 发车时间 | 北京站：每周三08:05 雅罗斯拉夫利站：每周二21:35 |
| 终到时间 | 雅罗斯拉夫利站：每周一13:58 北京站：每周一14:04 |
| 全程时间 | 130小时41分（K3次） 133小时31分（K4次） |
| 使用车体 | 中国铁路18型客车、中国铁路19型客车 |
列车时刻表
| 站次 | 站名 | 日期 | 到达时间 | 开车时间 |
|---|---|---|---|---|
| 1 | 北京 | 三 | 起点站 | 08：05 |
| 2 | 张家口南 | 三 | 11：20 | 11：26 |
| 3 | 大同 | 三 | 14：04 | 14：16 |
| 4 | 集宁南 | 三 | 16：03 | 16：09 |
| 5 | 朱日和 | 三 | 18：32 | 18：34 |
| 6 | 二连 | 三 | 20：37 | 23：59 |
| 7 | 扎门乌德 | 四 | 0：25 | 01：40 |
| 8 | 乌兰巴托 | 四 | 13：20 | 13：50 |
| 9 | 苏赫巴托 | 四 | 20：50 | 22：05 |
| 10 | 纳乌什基 | 四 | 19：14 | 22：31 |
| 11 | 乌兰乌德 | 五 | 02：39 | 03：09 |
| 12 | 伊尔库茨克 | 五 | 10：40 | 11：05 |
| 13 | 克拉斯诺雅尔斯克 | 六 | 03：54 | 04：04 |
| 14 | 新西伯利亚 | 六 | 15：58 | 16：18 |
| 15 | 鄂木斯克 | 六 | 23：29 | 23：49 |
| 16 | 斯维尔德诺夫斯克 | 日 | 11：30 | 11：50 |
| 17 | 别米尔 | 日 | 17：22 | 17：42 |
| 18 | 莫斯科 | 一 | 14：28 | 终点站 |
自2014年7月1日起施行新时刻表
| K3次 | 停靠站 | K4次 | ||||||
|---|---|---|---|---|---|---|---|---|
| 里程 | 天数 | 到点 | 开点 | 到点 | 开点 | 天数 | 里程 | |
| 0 | 星期三 | — | 11:22 | 北京 | 11:40 | — | 星期一 | 7692 |
| 196 | 星期三 | 14:39 | 14:45 | 张家口南 | 08:16 | 08:24 | 星期一 | 7496 |
| 374 | 星期三 | 16:56 | 17:08 | 集宁南 | 06:08 | 06:20 | 星期一 | 7318 |
| 548 | 星期三 | 19:38 | 19:40 | 朱日和 | 03:29 | 03:31 | 星期一 | 7144 |
| 707 | 星期三 | 21:48 | 00:59 | 二连 | 21:00 | 01:20 | 星期一 | 6985 |
| 717 | 星期四 | 01:25 | 02:40 | 扎门乌德 | 18:50 | 20:35 | 星期日 | 6975 |
| 952 | 星期四 | 06:15 | 06:35 | 赛音山达 | 14:42 | 15:20 | 星期日 | 6740 |
| 1179 | 星期四 | 09:58 | 10:19 | 乔伊尔 | 11:06 | 11:30 | 星期日 | 6513 |
| 1426 | 星期四 | 14:20 | 15:25 | 乌兰巴托 | 06:35 | 07:15 | 星期日 | 6266 |
| 1598 | 星期四 | 18:02 | 18:19 | 宗哈拉 | 03:30 | 03:45 | 星期日 | 6094 |
| 1707 | 星期四 | 20:19 | 20:24 | 达尔汗 | 01:22 | 01:44 | 星期日 | 5985 |
| 1805 | 星期四 | 21:50 | 23:05 | 苏赫巴托 | 22:10 | 23:55 | 星期六 | 5887 |
| 1828 | 星期四 | 19:14 | 21:04 | 纳乌什基 | 14:36 | 16:26 | 星期六 | 5864 |
| 1871 | 星期四 | 21:54 | 21:56 | 吉达 | 13:50 | 13:51 | 星期六 | 5821 |
| 2083 | 星期五 | 02:04 | 02:44 | 乌兰乌德 | 09:57 | 10:27 | 星期六 | 5609 |
| 2413 | 星期五 | 08:11 | 08:16 | 斯柳江卡 | 05:19 | 05:21 | 星期六 | 5279 |
| 2539 | 星期五 | 10:49 | 11:14 | 伊尔库茨克 | 02:28 | 02:53 | 星期六 | 5153 |
| 2790 | 星期五 | 15:04 | 15:34 | 集马 | 22:02 | 22:32 | 星期五 | 4902 |
| 3045 | 星期五 | 19:01 | 19:14 | 尼日涅乌丁斯克 | 18:17 | 18:30 | 星期五 | 4647 |
| 3348 | 星期五 | 23:40 | 00:02 | 伊兰斯卡雅 | 13:16 | 13:38 | 星期五 | 4344 |
| 3627 | 星期六 | 03:53 | 04:15 | 克拉斯诺雅尔斯克 | 08:45 | 09:07 | 星期五 | 4065 |
| 4012 | 星期六 | 09:54 | 10:20 | 马林斯克 | 02:59 | 03:25 | 星期五 | 3680 |
| 4160 | 星期六 | 12:22 | 12:24 | 泰加 | 00:57 | 00:59 | 星期五 | 3532 |
| 4389 | 星期六 | 15:53 | 16:12 | 新西伯利亚 | 21:04 | 21:23 | 星期四 | 3303 |
| 4692 | 星期六 | 19:33 | 20:00 | 巴拉宾斯克 | 17:27 | 17:57 | 星期四 | 3000 |
| 5016 | 星期六 | 23:26 | 23:46 | 欧姆斯克 | 13:37 | 13:53 | 星期四 | 2676 |
| 5299 | 星期日 | 02:51 | 03:03 | 伊施姆 | 10:22 | 10:34 | 星期四 | 2393 |
| 5588 | 星期日 | 06:31 | 06:51 | 秋明 | 06:18 | 06:38 | 星期四 | 2104 |
| 5914 | 星期日 | 11:15 | 11:42 | 斯维尔德洛夫斯克 | 01:32 | 01:59 | 星期四 | 1778 |
| 6295 | 星期日 | 17:16 | 17:36 | 彼尔姆 | 19:48 | 20:17 | 星期三 | 1397 |
| 6538 | 星期日 | 21:25 | 21:48 | 巴列集诺 | 15:43 | 16:06 | 星期三 | 1154 |
| 6775 | 星期一 | 00:51 | 01:06 | 基洛夫 | 12:18 | 12:33 | 星期三 | 917 |
| 7231 | 星期一 | 06:50 | 07:02 | 高尔基 | 05:36 | 05:48 | 星期三 | 461 |
| 7482 | 星期一 | 10:20 | 10:43 | 弗拉基米尔 | 02:30 | 02:53 | 星期三 | 210 |
| 7692 | 星期一 | 13:58 | — | 莫斯科 | — | 23:45 | 星期二 | 0 |
