A server includes a scanning module for determining whether an application is free of malware, a module for packaging the application into blocks for delivery via application streaming, a module for providing the blocks to a client on request, and a module for adding to each block an indication of whether the associated application has already been determined to be free of malware. A client includes a module for requesting blocks of a streamed application from the server. When the client receives a block, it employs a module for verifying that the associated applications have been determined to be free of malware by examining the indication provided by the server. If verification is successful, then the block's code is executed without first receiving and scanning any additional blocks from the server.