Gospel Parallels
We must never neglect parallel accounts, since they often include details which preclude certain interpretations of their counterparts (that is, one may interpret Matthew, for example, to be saying one thing, which, when read in light of the parallel, cannot possibly be true). This is crucial to understanding the authentic meaning of either.
Matthew's Account
So we have Matthew's account:
Matthew 28:16-20 (DRB)
And the eleven disciples went into Galilee, unto the mountain where Jesus had appointed them. 17 And seeing him they adored: but some doubted. 18 And Jesus coming, spoke to them, saying: All power is given to me in heaven and in earth. 19 Going therefore, teach ye1 all nations; baptizing them in the name of the Father, and of the Son, and of the Holy Ghost. 20 Teaching them to observe all things whatsoever I have commanded you: and behold I am with you all days, even to the consummation of the world.
But pretending for now that we have only Matthew's account (so that we can compare with the parallel and amend any errors) it's evident that baptism is at least an integral if not absolutely essential part of teaching the nations Christianity—or rather an essential part of making disciples of Jesus. The use of the participle “baptizing” is significant, because it indicates a disambiguation of what was stated before: “make disciples of all nations.” That is, by “teach ye all nations” Jesus means “baptize them, and teach them to observe everything I have commanded.” Here, baptism is of central and primary importance (concordant with traditional Christian teaching).
This explains satisfyingly the teaching of the prince of the Apostles, where Peter, as Jesus, who equates, conflates and includes baptism with acceptance of the gospel:
Acts 8:37-28 (DRB) Now when they had heard these [i.e. incriminating, conscience-rending] things, they had compunction in their heart, and said to Peter, and to the rest of the apostles: What shall we do, men and brethren? 38 But Peter said to them: [Repent], and be baptized every one of you in the name of Jesus Christ, for the remission of your sins: and you shall receive the gift of the Holy Ghost.
Notice he doesn't equate belief with 'not doing' anything ('just assent'). He says 'repent and be baptized and you will have your sins for given'—for that's the force of the grammar).
Here the line between repentance and the baptism which follows is not blurred so much as repentance is defined as incomplete without baptism, the necessary consequence.
After all, the Apostle Paul (the earliest of the New Testament authors) wrote that baptism is when we put on Christ (as a garment specifically):2
Galatians 3:26-27 (DRB) For you are all the children of God by faith, in Christ Jesus. 27 For as many of you as have been baptized in Christ, have put on Christ.
And lest we should think this is how we 'radically identify' merely with Christ after 'having been saved,' he puts to rest this misinterpretation. That is, lest we are said to have put on Christ before baptism (or worse: that before baptism we have not put on Christ but have appropriated His saving work nonetheless, making putting on Christ effectively redundant), baptism is defined as the new circumcision made without hands (i.e. circumcision in spirit):3
Colossians 2:11-12 (DRB) In whom also you are circumcised with circumcision not made by hand, in despoiling of the body of the flesh, but in the circumcision of Christ: 12 Buried with him in baptism, in whom also you are risen again by the faith of the operation of God, who hath raised him up from the dead.
That is, we are not buried with him and raised to life with Him unless we are baptized (else we empty the words 'we are raised to life with Him' of all true meaning).
Romans 6:3-4 (DRB) Know you not that all we, who are baptized in Christ Jesus, are baptized in his death? 4 For we are buried together with him by baptism into death; that as Christ is risen from the dead by the glory of the Father, so we also may walk in newness of life.
Again and again baptism, by Christ as well as Apostle—and strictly "as many as have been baptized"—is viewed as the fulfillment and constitution of a saving repentance and faith in Christ.
Mark's Account
Now Mark's account only agrees with this:
Mark 16:14-16 (DRB)
At length he appeared to the eleven as they were at table: and he upbraided them with their incredulity and hardness of heart, because they did not believe them who had seen him after he was risen again. 15 And he said to them: Go ye into the whole world, and preach the gospel to every creature. 16 He that believeth and is baptized, shall be saved: but he that believeth not shall be condemned.
Here in Mark,4 we have more words of Jesus: “He who believes and is baptized shall be saved.” This makes baptism an essential act once you believe ("but he who believes not" includes “and is not baptized”—“and is not baptized” would be redundant for the same reason, 'he who is atheist and belies not in God' is redundant—whoever is atheist, it follows, is not a believer: whoever truly believes will baptized; those who don't will see not need to, and so will not be, whence it follows that it is redundant to say 'he who believes not and is not baptized, because he doesn't believe'). This is also corroborated in Acts, where the preaching of the Gospel seems to have intrinsically included baptism as an essential part of it:
Acts 8:34-36 (DRB) And the eunuch answering Philip, said: I beseech thee, of whom doth the prophet speak this? of himself, or of some other man? 35 Then Philip, opening his mouth, and beginning at this scripture, preached unto him Jesus. 36 And as they went on their way, they came to a certain water; and the eunuch said: See, here is water: what doth hinder me from being baptized?
To say anything other than 'Jesus taught that you must believe and be baptized to be saved' is literally to say 'He who believes and is baptized' is equivalent to 'he who believes and is not baptized' shall be saved—which is just a basic grammar issue, before we even dream of qualifying it for theologically viable.
Whence the teaching of Jesus is clear, and has always been understood as I have above described by the Christian Church.
Appendix
St. Paul taught that right doctrine believed is necessary for salvation:
1 Timothy 4:16 (DRB) Take heed to thyself and to doctrine: be earnest in them. For in doing this thou shalt both save thyself and them that hear thee.
Footnotes
1 Or “disciple all nations”
2 Cf. Mt 22:1; Rev 19:9/ Rev 19:8; Mt 22:12-13
3 Cf. Ezek 36:25-26; Heb 10:22; Eph 5:26; Titus 3:5; etc.
4 The so-called 'addition of Mark' can be variously explained, including imperfect or hurried or mistaken transmission: not only by addition; and as an argument in support of its not being an addition, the material "the eleven as they sat at table" seems on the surface to contradict Matthew's account, where no mention of being sat at table is mentioned, only recourse to the mountain appointed by Jesus: it also has nowhere to be from, and in any case agrees with the faith professed by those through whose hands alone we have received Matthew and the rest of Mark to begin with.