In this thesis, we work towards improving two important aspects of deep neural networks via a probabilistic point of view; the uncertainty in their predictions and their efficiency as computational models. On the uncertainty side, we propose posterior approximations for variational Bayesian neural networks, that consider either linear or non-linear dependencies between the elements of the weight matrices. We then continue in adopting a different view and consider Bayesian models in the function space, i.e. stochastic processes, that employ the flexibility of deep neural networks in their construction. On the efficiency side, we start by showing how Bayesian inference through specific choices for the prior distributions over the parameters can lead to highly compressed models through joint pruning and quantization. We then tease these two objectives apart and take a closer look at sparsity and quantization by proposing two general purpose recipes that can allow for gradient based optimization of such objectives. Finally, we conclude this thesis by providing a discussion on the research outcomes and the challenges we encountered, along with promising directions for future work.