The low crystallinity of arsenic (As) containing minerals such as arseniosiderite and yukonite has made a detailed understanding of their atomic structures elusive. X-ray pair distribution function (PDF) and transmission electron microscopy (TEM) were used to gain a detailed understanding of the short and medium-range structural features. High-resolution synchrotron powder diffraction data showed long-range order in arseniosiderite occurs along one direction. PDF data confirmed arseniosiderite has the same general structure as robertsite and mitridatite but with the layers occasionally shifted to disrupt long-range order. Use of small box and reverse Monte Carlo modeling of the PDF data gave the first complete set of atomic coordinates for arseniosiderite. TEM confirmed the degree of interlayer order is generally high. PDF and TEM data show that yukonite is a nano-sized analog of arseniosiderite which lacks any long-range order but is locally similar. The structural evolution of arseniosiderite from yukonite was observed for the first time in a natural specimen via TEM. PDF data on several yukonite samples reveal rather sudden drops in the degree of structural correlation as a function of distance. These drops occur from yukonite being composed of small layers made of integer numbers of large nonamers of edge-sharing FeO6 octahedra, as seen in arseniosiderite. However, these layers are 2 or 3 nonamers in width, with little structural correlation between layers. Thus our work provides a more complete nano/microscopic picture of the key structural features in these minerals found in mining ores and wastes around the world.