According to Reformed Baptist theology, when did the Church begin? In the Old Testament or in the New Testament?
Reformed theologians, including Reformed Baptists, typically believe that the church includes all true believers of all time, both Old Testament and New Testament.
This view naturally follows from covenant theology, which argues that there is one covenant, a covenant of grace, that has been in effect ever since the Fall.
Let's review the writings of a few Reformed Baptists from various eras. We can start with one of the first documents of Reformed Baptists, the 1689 Baptist Confession of Faith:
The universal Church, which may be called invisible (in respect of the internal work of the Spirit and truth of grace) consists of the entire number of the elect, all those who have been, who are, or who shall be gathered into one under Christ, Who is the Head. This universal Church is the wife, the body, the fullness of Him Who fills all in all. (26.1)
Another section makes it clear that the writers of this confession considered the elect to come from both the Old and New Testament periods, since it refers to "true believers under the Old Testament law" (21.1). A later writer, A. H. Strong (1836–1921), elaborates a bit:
The church of Christ, in its largest signification, is the whole company of regenerate persons in all times and ages, in heaven and on earth. In this sense, the church is identical with the spiritual kingdom of God; both signify that redeemed humanity in which God in Christ exercises actual spiritual dominion. (Systematic Theology, VII.1)
Wayne Grudem (1948–) shares the same understanding and specifically calls out the Old and New Testaments:
The church is the community of all true believers for all time. [...] Even though there are certainly new privileges and new blessings that are given to the people of God in the New Testament, both the usage of the term "church" in Scripture and the fact that throughout Scripture God has always called his people to assemble to worship himself, indicate that it is appropriate to think of the church as constituting all the people of God for all time, both Old Testament believers and New Testament believers. (Systematic Theology, chapter 44)