The results are important because they shed light on how habitable Mars was billions of years ago, and how long any surface water persisted.
Details have been published in the journal Nature Geoscience.
The scientists calculated the early Martian atmospheric pressure using patterns of ancient meteor craters and dry river beds seen on its surface today.
They used new Mars orbiter data to test out an idea first proposed by Carl Sagan more than 20 years ago - that atmospheric pressure is recorded by the size of the smallest impact craters.
The ancient Martian climate is inferred from the landscape of water-sculpted lakes and river beds seen today. They show that liquid water must have existed on its surface early in the planet's history.
The new result, however, implies that Mars was not a permanently warm wet world and that periods of arid, sub-zero conditions existed.
River channels at Aeolis Dorsa, near Gale Crater on Mars, interweave with impact craters, and it is the smallest of these craters that are key to the new findings.
The craters sit within riverbeds thought to be about 3.6 billion years old.
On planets with a thick atmosphere, small meteors break up and burn as fireballs, never reaching the ground. But some of the craters at Aeolis Dorsa are only a few tens of metres across, suggesting that quite small meteors made it through the thin atmosphere.
Into thin air The result raises questions about just how habitable Mars was billions of years ago, and how long any surface water persisted.
"Our work has nudged me towards thinking that the conditions were mostly very cold and very dry even on early Mars - similar to (Earth's) Antarctic Dry Valleys today," lead author Dr Edwin Kite told BBC News.
"However, there is still plenty of microbial life even in the Antarctic Dry Valleys so our work doesn't rule out an early environmental niche for life on Mars."
Although this method for measuring limits of atmospheric pressure on Mars was suggested a couple of decades ago, it has only recently become possible with the advent of high resolution images of the surface from extended missions like Nasa's Mars Reconnaissance Orbiter.
"The density of the atmosphere controls climate. And climate, in particular temperature, determines whether liquid water can exist on the surface" said Prof Michael Manga of the University of California, Berkeley, who was not involved in the study.
"Their inferred atmospheric pressure is low enough that the greenhouse gas would not have been strong enough for liquid water to exist, except under the right combination of rare orbital conditions."
Since the craters exist with rivers, water was clearly flowing at some point. But it seems from these results that surface water was not permanently present on early Mars, and that periods when the temperature got above freezing were rare or periodic.
Similar conclusions are suggested in a separate study published in the journal Geology this week, where Steven Ruff, from Arizona State University, reports that the chemical signature of early Mars minerals analysed by Nasa's Mars Exploration Rover Spirit indicates they formed as an ephemeral lake dried out.
The latest study shows how Martian environments from billions of years ago can be pieced together from evidence on its surface today.
Here on Earth, fossilised raindrop imprints that fell almost three billion years ago have been used to infer our early atmosphere. Scientists like Dr Kite will doubtless be looking out for such clues in any new results from explorations of the Red Planet.