An analysis is carried out to study the magnetohydrodynamic (MHD) flow and heat transfer characteristics of an electrically conducting dusty non-Newtonian fluid, namely, the upper convected Maxwell (UCM) fluid over a stretching sheet. The stretching velocity and the temperature at the surface are assumed to vary linearly with the distance from the origin. Using a similarity transformation, the governing nonlinear partial differential equations of the model problem are transformed into coupled non-linear ordinary differential equations and the equations are solved numerically by a second order finite difference implicit method known as the Keller-box method. Comparisons with the available results in the literature are presented as a special case. The effects of the physical parameters on the fluid velocity, the velocity of the dust particle, the density of the dust particle, the fluid temperature, the dust-phase temperature, the skin friction, and the wall-temperature gradient are presented through tables and graphs. It is observed that, Maxwell fluid reduces the wall-shear stress. Also, the fluid particle interaction reduces the fluid temperature in the boundary layer. Furthermore, the results obtained for the flow and heat transfer characteristics reveal many interesting behaviors that warrant further study on the non-Newtonian fluid flow phenomena, especially the dusty UCM fluid flow phenomena.