At the risk of perhaps adding some confusion...
malloc is a regular C-function. Because it is C, it can only signal errors by ways that fit into a C program: using the return value, an argument passed by pointer or a global variable (like errno).
new introduces a C++ expression, it calls the operator new to obtain memory and then constructs the object. Either the operator new or the constructors may throw.
Note: there is a no throw version of the new expression
Most operator new are generally implemented in term of malloc, but as I noted there is more to a new expression than simply getting memory, since it's also builds the object(s).
It also takes care of managing up until it releases it to you. That is, if the constructor throws, then it properly disposes of the memory that was allocated, and in case of the new[] expression (which builds an array), calls the destructor of those objects that were already built.
Regarding stack overflows: it depends on your compiler and your operating system. The OS might remark the issue and signals the error, the compiler might check etc...
Note that gcc introduces the split-stack option to compiling, which consists in allocating a minimal stack and then growing it on demand. This neatly sidesteps the issue of possible stack-overflows, but introduces yet another binary compatibility issue since interaction with code that was not built with this option could get hazy; I don't know how they plan on implementing this exactly.