Paul said that they preached Christ crucified (1 Cor. 1:23). It also seems that Paul's starting point in the gospel message was different, depending on whether he was speaking with Jews or with Gentiles. With Jews, apparently he reasoned out of the Scriptures (Old Testament), but with Gentiles his starting point was not the Scriptures (special revelation) but rather their innate knowledge of God (general revelation), as is evident in Acts 17:22-31. This seems to be in line with his declaration in 1 Cor. 9:20-23 of becoming "all things to all people ... for the sake of the gospel."
It's clear from Scripture that in the ministries of Jesus and the apostles, the common denominator underlying everything they did was proclamation of the truth. This was a non-negotiable element for them. They never shoved the truth into the background or made it step 2 of their evangelism.